package Tree.ThreadedBinaryTree;

public class Tree {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        Hero hero1 = new Hero(1, "宋江");
        Hero hero2 = new Hero(3, "吴用");
        Hero hero3 = new Hero(6, "卢俊义");
        Hero hero4 = new Hero(8, "林冲");
        Hero hero5 = new Hero(10, "关胜");
        Hero hero6 = new Hero(14,"鲁智深");
        hero1.setLeft(hero2);
        hero1.setRight(hero3);
        hero2.setLeft(hero4);
        hero2.setRight(hero5);
        hero3.setLeft(hero6);
        binaryTree.toThreadedBT(hero1);
        binaryTree.setRoot(hero1);
        Hero left = hero5.getLeft();
        System.out.println(left);
        System.out.println(111);
        binaryTree.printBinaryTree();
    }
}
//创建树
class BinaryTree{
    private Hero root;
    //为了实现线索化需要创建一个指向当前结点的前驱结点的指针
    public void printBinaryTree(){
        Hero hero = root;
        while (hero!=null){

            //找到前驱结点不为0的
            while (hero.getLeftType()==0){
                hero=hero.getLeft();
            }

            System.out.println(hero.toString());

            while (hero.getRightType()==1){
                hero = hero.getRight();
                System.out.println(hero.toString());
            }
            hero=hero.getRight();
        }
    }
    //在递归现实化时，总是保留前一个结点
    private Hero pre = null;
    ///线索化二叉树：
    public void toThreadedBT(Hero hero){

        if (hero==null){
            return;
        }
        //先线索化左子树
        if (hero.getLeft()!=null){
            toThreadedBT(hero.getLeft());
        }
        //线索化当前结点
          //处理当前结点的前驱结点
        if(hero.getLeft()==null){
            //让当前的做左指针指向前驱结点
            hero.setLeft(pre);
            hero.setLeftType(1);
        }
        //处理当前结点的后继结点
        if(pre!=null&&pre.getRight()==null){
            pre.setRight(hero);
            pre.setRightType(1);
        }
        pre=hero;
        //线索化右子树
        if(hero.getRight()!=null){
            toThreadedBT(hero.getRight());
        }

    }

    //根节点
    public void setRoot(Hero root) {
        this.root = root;
    }


    //前序遍历：
    public void preOrder(){
        if(root!=null){
            root.preOrder();
        }else {
            System.out.println("当前二叉树为空~~~~");
        }
    }
    //中序遍历：
    public void minOrder(){
        if(root!=null){
            root.minOrder();
        }else {
            System.out.println("当前二叉树为空~~~~");
        }
    }
    //后序遍历：
    public void latterOrder(){
        if(root!=null){
            root.latterOrder();
        }else {
            System.out.println("当前二叉树为空~~~~");
        }
    }
    //前查找：
    public Hero preSeach(int no){
        if(root!=null){
            return root.preReseachNo(no);
        }else {
            return null;
        }
    }
    public Hero minSeach(int no){
        if(root!=null){
            return root.minReseachNo(no);
        }else {
            return null;
        }
    }
    public Hero latterSeach(int no){
        if(root!=null){
            return root.latterReseachNo(no);
        }else {
            return null;
        }
    }
    public void deleteByno(int no) {
        if (root == null) {
            System.out.println("这是空树，无法删除");
        } else {
            if (root.getHeroNo() == no) {
                root = null;
                return;
            } else {
                root.deleteTreeByNo(no);
            }
        }
    }
}
//
class Hero{
    private int heroNo;
    private String eroName;
    private Hero Left;
    private Hero Right;
    //0代表子树 1代表前驱或者后继
    private int LeftType;
    private int RightType;
    public Hero(int heroNo, String eroName) {
        this.heroNo = heroNo;
        this.eroName = eroName;
    }

    public int getHeroNo() {
        return heroNo;
    }

    public void setHeroNo(int heroNo) {
        this.heroNo = heroNo;
    }

    public String getEroName() {
        return eroName;
    }

    public void setEroName(String eroName) {
        this.eroName = eroName;
    }

    public Hero getLeft() {
        return Left;
    }

    public void setLeft(Hero left) {
        Left = left;
    }

    public Hero getRight() {
        return Right;
    }

    public void setRight(Hero right) {
        Right = right;
    }

    public int getLeftType() {
        return LeftType;
    }

    public void setLeftType(int leftType) {
        LeftType = leftType;
    }

    public int getRightType() {
        return RightType;
    }

    public void setRightType(int rightType) {
        RightType = rightType;
    }

    @Override
    public String toString() {
        return "Hero{" +
                "heroNo=" + heroNo +
                ", eroName='" + eroName + '\'' +
                '}';
    }
    //前序输出
    public void preOrder(){
        System.out.println(this);
        if(this.getLeft()!=null){
            this.getLeft().preOrder();
        }
        if(this.getRight()!=null){
            this.getRight().preOrder();
        }
    }
    //中序输出
    public void minOrder(){
        if(this.getLeft()!=null){
            this.getLeft().minOrder();
        }
        System.out.println(this);
        if (this.getRight()!=null){
            this.getRight().minOrder();
        }
    }
    //后序输出
    public void latterOrder(){
        if(this.getLeft()!=null){
            this.getLeft().minOrder();
        }
        if (this.getRight()!=null){
            this.getRight().minOrder();
        }
        System.out.println(this);
    }
    //前查找
    public Hero preReseachNo(int no){
        System.out.println("进入了前序遍历~~");
        if(this.getHeroNo()==no){
            return this;
        }
        Hero hero=null;
        if (this.getLeft()!=null){
            hero=this.getLeft().preReseachNo(no);
        }
        if (hero!=null){
            return hero;
        }
        if (this.getRight()!=null){
            hero = this.getRight().preReseachNo(no);
        }
        if (hero!=null){
            return hero;
        }
        return hero;
    }
    //后查找
    public Hero minReseachNo(int no){
        Hero hero=null;
        if (this.getLeft()!=null){
            hero=this.getLeft().minReseachNo(no);
        }
        if (hero!=null){
            return hero;
        }
        System.out.println("进入了中序遍历~~");
        if (this.getHeroNo()==no){
            return this;
        }
        if (this.getRight()!=null){
            hero = this.getRight().minReseachNo(no);
        }
        if (hero!=null){
            return hero;
        }
        return hero;
    }
    public Hero latterReseachNo(int no){
        Hero hero = null;
        if (this.getLeft()!=null){
            hero = this.getLeft().latterReseachNo(no);
        }
        if (hero!=null){
            return hero;
        }
        if (this.getRight()!=null){
            hero = this.getRight().latterReseachNo(no);
        }
        if (hero!=null){
            return hero;
        }
        System.out.println("进入了后序遍历");
        if (this.getHeroNo()==no){
            return this;
        }
        return hero;
    }
    //删除节点:
    public void deleteTreeByNo(int no){
        if(this.getLeft()!=null){
            if (this.getLeft().getHeroNo()==no){
                this.setLeft(null);
                return;
            }
        }
        if(this.getRight()!=null){
            if (this.getRight().getHeroNo()==no){
                this.setRight(null);
                return;
            }
        }
        if (this.getLeft()!=null){
            this.getLeft().deleteTreeByNo(no);
        }
        if (this.getRight()!=null){
            this.getRight().deleteTreeByNo(no);
        }
    }
}